This invention relates to a storage device and an accessing method, and particularly to a block erase type storage device and an accessing method for the same.
A block erase type storage device is known which comprises a block erase type storage medium such as a flash memory, and which reads and writes information under the control of a central processing unit (CPU) and a dedicated controller.
The block erase type storage medium indicates such a storage medium that the storage contents of a writing target area need to be erased in advance in order to write data therein and an erasing process can be performed only in units (generally called blocks) equal to or larger than the smallest unit (generally called a page, a segment or the like) of the storage capacity dealt in a writing process.
In order to manage an external access, the block erase type storage device comprises an SRAM (Static Random Access Memory) or the like which stores an empty block table in which information representing the locations of empty blocks is stored and an address translation table in which information showing the correspondence between logical and physical addresses is stored.
Upon reception of a write request, the block erase type storage device finds an empty block registered in the empty block table, writes data in the found block, adds the correspondence between the physical and logical addresses of the block to the address translation table, and furthermore, erases the block from the empty block table.
Moreover, upon reception of a read request, the block erase type storage device searches the address translation table while using the logical address of to-be-read data as a key, discriminates the physical address of the location at which the to-be-read data has been stored, and reads the data from that location.
In to such a storage device, the volume of the entire storage device increases according to the volume occupied by the SRAM. Due to this, such a storage device when used for purposes which require a small volume as in the case of a JEIDA/PCMCIA card, etc., needs a volume suppressing idea.
Furthermore, the SRAM consumes a large amount of power, and if the SRAM is used to store a variety of tables, the amount of power consumed by the entire storage device increases, entailing a drawback of the storage device becoming unsuitable for being applied to purposes which require low power consumption as in the case of a JEIDA/PCMCIA card, etc.
This invention has been made in consideration of the above-described circumstances, and an object thereof is to provide a block erase type storage device of a small volume and low power consumption and an accessing method for the same.
A storage device according to the first aspect of this invention having the above object is characterized by comprising:
storage means (1), including a plurality of memory blocks to which physical addresses have been assigned;
erasure means (1e) for batch erasing of stored data from the storage means in units of memory blocks; and
writing means (4X, 4B, 5, 20), to which data and logical addresses are input, for determining locations where the data is to be stored in the storage means and for writing the data in the locations;
wherein the storage means stores an address translation table which stores information showing a correspondence between the logical addresses and physical addresses of the storage means, and
the writing means comprises means (4X, 4B, 5, 20) for adding, to the address translation table, information showing a correspondence between physical addresses of the locations where the data has been written and the input logical addresses, or for updating the address translation table.
According to the storage device having this structure, the address translation table is stored in the storage means which is a block erase type storage medium. Therefore, a storage medium such as an SRAM or the like for storing the address translation table is not required in addition to the aforementioned storage means. This ensures a block erase type storage device whose volume is relatively small and whose power consumption is low.
The above-described storage device may further comprise reading means (4X, 4B, 5, 20) including:
means (20) for storing a physical address of a block in which the address translation table has been written;
physical address reading means (4X, 4B, 5, 20) for accessing the block which contains the address translation table stored therein and for reading physical addresses corresponding to logical addresses of to-be-read data; and
means (4X, 4B, 5, 20) for reading and outputting data stored at the physical addresses read by the physical address reading means.
Using this reading means, the physical addresses of the to-be-read data can be detected and read from the address translation table stored in the storage means.
The aforementioned storage means can store an empty block table which stores information specifying empty blocks containing no data stored therein.
By employing this structure, the used amount of memory such as an SRAM or the like, utilized in addition to the storage means, can be further reduced to promote a reduction in the volume and power consumption.
The empty block table which stores information specifying the empty block that has been existed until the data has been stored in the empty block is eliminated, and the empty block table which stores information specifying empty blocks that remain after the empty block writing means has written the data in the empty block is stored in the storage means. By so doing, information on the empty blocks contained in the empty block table is updated so that the up-to-date empty block information can be attained at any time.
The aforementioned storage means may comprise a plurality of chips or flash memories, for example. In this case, the address translation table (and the empty block table) may be stored in an arbitrary block of any one of the chips or flash memories. And means may be provided for storing information showing in which block of which chip the address translation table and the empty block table have been stored.
The storage means stores the address translation table and the empty block table in one block.
According to this structure, the number of blocks for storing the address translation table and the empty block table can be minimized to one, and the storage capacity of the storage means can be used with efficiency. Moreover, the management of the locations at which those tables have been stored becomes easy.
Further, a storage device according to the second aspect of this invention is characterized by comprising:
storage means (1), including a plurality of memory blocks to which physical addresses have been assigned;
erasure means (1e) for batch erasing of stored data from the storage means in units of memory blocks; and
writing means (4X, 4B, 5, 20), to which to-be-written data and logical addresses are input, for determining locations where the data is to be stored in the storage means and for writing the data in the locations;
wherein the storage means stores empty block information specifying empty blocks in which the data is not stored, and
the writing means writes the data in an empty block specified by the empty block information.
According to this structure, the empty block information is stored in the storage means which is a block erase type storage medium. Therefore, a storage medium such as an SRAM or the like for storing the empty block information is not required in addition to the aforementioned storage means. This ensures a block erase type storage device whose volume is relatively small and whose power consumption is low.
If the writing means further comprises updating means (1e, 4X, 4B, 5, 20) for changing the empty block information stored in the storage means to the empty block information which specifies information on empty blocks that remain after the writing means has written the data in the empty block, the empty block information is updated so that the up-to-date empty block information can be attained at any time.
The empty block information may be stored in a portion of each empty block, and includes chain information registered to specify another empty block in a chain manner. In this case, the writing means may comprise means (4X, 4B, 5, 20) for detecting an empty block in accordance with the chain information and for writing the data in the empty block.
According to this structure, one block need not be used to store the empty block table, and the efficiency of use of the storage medium is high. Moreover, since a writing target block is specified based on the chain information on empty blocks, the frequency of use of each block is uniformized.
When the empty block information includes the chain information, top empty block storing means (20), etc. may be provided for storing an address of a first empty block; data may be written in the empty block assigned the physical address stored in the top empty block storing means; and the contents of the top empty block storing means can be updated by the chain information registered in the block in which the data has been written.
In the case where the storing means comprises a flash memory or the like, its storage area comprises data areas and redundant areas. In this case, the chain information can be stored in the redundant areas.
In such a storage device, the chain information is written in the redundant areas of the empty blocks, and the aforementioned data is overwritten in the empty blocks in which the chain information has already been written.
In this case, the data areas and the redundant areas are arranged so as not to overlap each other in the aforementioned storage area, thereby preventing the chain information from being destroyed due to the overwriting of the aforementioned data.
Similarly in the storage device according to the second embodiment, the storage means may comprise a plurality of chips or flash memories, for example. In this case, the chain information may include information showing in which block of which chip the next block has been stored.
An accessing method according to the third aspect of this invention is a method for accessing a memory of a block erase type in which data can be erased in units of blocks and data can be written in empty blocks from which data has been erased in advance, and the method is characterized by comprising steps of:
causing the memory itself to store an address translation table which stores information showing a correspondence between physical addresses assigned to the memory and logical addresses of data;
at a time of supply of to-be-written data and their logical addresses, making a determination based on the address translation table as to whether data has already been written at the logical addresses, and when it is determined that data exists at the logical addresses, detecting the empty blocks, writing the data in the empty blocks and erasing blocks containing old data, while when it is determined that no data exists at the logical addresses, detecting the empty blocks, writing the data in the empty blocks, and thereafter;
adding information showing a correspondence between physical addresses of the blocks in which the data has been written and the logical addresses to the address translation table in the memory, or updating the information; and
at a time of supply of logical addresses of to-be-read data, accessing the address translation table in the memory, detecting physical addresses of locations where the data has been written, reading the data from the physical addresses, and outputting the data.
An accessing method according to the fourth aspect of this invention is a method for accessing a memory of a block erase type in which data can be erased in units of blocks and data can be written in empty blocks from which data has been erased in advance, and the method is characterized by comprising steps of:
causing the memory to store an empty block table specifying the empty blocks;
at a time of supply of to-be-written data, detecting an empty block on the basis of the empty block table in the memory, and writing the data in the detected empty block.
With the accessing methods according to the third and fourth aspects, parts of the memory can be used as the address translation table and the empty block table, and another memory such as an SRAM or the like for storing those tables need not be arranged, which contributes toward a reduction in the capacity and power consumption.
An accessing method according to the fifth aspect of this invention is a method for accessing a memory of a block erase type in which data can be erased in units of blocks and data can be written in empty blocks from which data has been erased in advance, and the method is characterized by comprising steps of:
causing a block which the memory comprises to store empty block information specifying the empty blocks of the memory;
at a time of supply of to-be-written data, detecting an empty block on the basis of the empty block information, writing the data in the detected empty block, newly detecting an empty block on the basis of the empty block information, erasing storage contents of the block in which the empty block information has been stored, and writing updated empty block information in the newly detected empty block.
With the accessing method according to the fifth aspect, not only parts of the memory can be used as the address translation table and the empty block table in order to achieve a reduction in the volume and power consumption, but also the empty block information can be updated so that the latest empty block information can be attained at any time.
An accessing method according to the sixth aspect of this invention is a method for accessing a memory of a block erase type in which data can be erased in units of blocks and data can be written in empty blocks from which data has been erased in advance, and the method is characterized by comprising steps of:
storing, in a portion of each empty block of the memory, empty block chain information which includes information that sequentially specifies another empty block; and
at a time of supply of to-be-written data, detecting a top empty block in an empty block chain defined by the empty block chain information, and writing the data in the detected empty block.
With the accessing method according to the sixth aspect, a part of the memory can be used as the empty block table. Furthermore, since the empty blocks in which data is to be written are in the order of the chain defined by the chain information, the writing frequency can be uniformized over the entirety of the memory.